package site.wanjiahao.tree;

import site.wanjiahao.printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;

// 前序遍历: 打印二叉树
// 中序遍历：元素降序或者升序
// 后序遍历: 先子节点后父节点操作
// 通用二叉树
public class BinaryTree<E> implements BinaryTreeInfo {

    // 容量大小
    protected int size;

    // 指向根节点
    protected Node root;

    // 前序遍历
    public void preorderTraversal(Consumer<E> consumer) {
        if (consumer == null) return;
        preorderTraversal(root, consumer);
    }

    public void preorderTraversal(Node node, Consumer<E> consumer) {
        // 1.递归出口
        if (node == null) return;
        if (consumer.isStop) return;
        // 外部自自定义消费逻辑
        consumer.isStop = consumer.accept(node.ele);

        // 明确函数作用是什么，遍历当前拿到的节点
        preorderTraversal(node.left, consumer);
        preorderTraversal(node.right,  consumer);
    }

    // 中序遍历
    public void inorderTraversal(Consumer<E> consumer) {
        if (consumer == null) return;
        inorderTraversal(root, consumer);
    }

    public void inorderTraversal(Node node, Consumer<E> consumer) {
        // 1.递归出口
        if (node == null || consumer.isStop) return;
        inorderTraversal(node.left, consumer);
        if (consumer.isStop) return;
        consumer.isStop = consumer.accept(node.ele);
        // 明确函数作用是什么，遍历当前拿到的节点
        inorderTraversal(node.right, consumer);
    }

    // 后序遍历
    public void postorderTraversal(Consumer<E> consumer) {
        postorderTraversal(root, consumer);
    }

    public void postorderTraversal(Node node, Consumer<E> consumer) {
        // 1.递归出口
        if (node == null || consumer.isStop) return;

        // 明确函数作用是什么，遍历当前拿到的节点
        postorderTraversal(node.left, consumer);
        postorderTraversal(node.right, consumer);
        if (consumer.isStop) return;
        consumer.isStop = consumer.accept(node.ele);
    }

    // 层序遍历
    public void levelOrderTraversal(Consumer<E> consumer) {
        // 遍历完每一层，如何遍历完每一层，将读出的数据放入队列中
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();

            boolean isInterrupt = consumer.accept(node.ele);
            if (isInterrupt) return;

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    // 计算二叉树的高度，采用层序遍历，可以计算二叉树的高度
    public int treeHeight() {
        if (root == null) return 0;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        int levelSize = 1;
        int height = 0;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            levelSize--;

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }

            if (levelSize == 0) {
                // 当前层遍历完成
                levelSize = queue.size();
                height++;
            }
        }
        return height;
    }

    public int nodeHeight(Node node) {
        if (node == null) return 0;

        return 1 + Math.max(nodeHeight(node.left), nodeHeight(node.right));
    }

    // 判断一个二叉树是否为完全二叉树
    public boolean isComplete() {
        boolean isLeaf = false;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();

            if (isLeaf && (node.left != null || node.right != null)) return false;

            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                // 左子树为空，右子树不为空，肯定不是完全二叉树
                return false;
            } else {
                // 左书不为空，右树为空，叶子节点判断
                isLeaf = true;
            }

            if (node.right != null) {
                queue.offer(node.right);
            } else {
                // 判断后续节点是否存在叶子节点，存在则不是完成二叉树，不存在者是
                isLeaf = true;
            }
        }
        return true;
    }

    // 前驱节点
    protected Node predecessor(Node node) {
        // 当前节点是否有左节点
        if (node.left != null) {
            node = node.left;
            while (node.right != null) {
                node = node.right;
            }
            // 循环终止，当前节点为前驱节点
            return node;
        } else if (node.parent != null) {
            // 父节点的右节点为当前节点，则为前驱节点
            while (node.parent != null && node.parent.right != node) {
                node = node.parent;
            }
            return node.parent;
        } else {
            // 左节点也为空，父节点为空，无前驱节点
            return null;
        }
    }

    // 后继节点
    protected Node successor(Node node) {
        // 当前节点是否有左节点
        if (node.right != null) {
            node = node.right;
            while (node.left != null) {
                node = node.left;
            }
            // 循环终止，当前节点为前驱节点
            return node;
        } else if (node.parent != null) {
            // 父节点的右节点为当前节点，则为前驱节点
            while (node.parent != null && node.parent.left != node) {
                node = node.parent;
            }
            return node.parent;
        } else {
            // 左节点也为空，父节点为空，无前驱节点
            return null;
        }
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        root = null;
        size = 0;
    }

    protected boolean hasTwoChildren(Node node) {
        return node.left != null && node.right != null;
    }

    protected boolean nonChildren(Node node) {
        return node.left == null || node.right == null;
    }

    protected Node createNode(E ele, Node parent) {
        return new Node(ele, parent);
    }


    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node) node).right;
    }

    @Override
    public Object string(Object node) {
        return node;
    }

    // 消费者类
    public static abstract class Consumer<E> {

        boolean isStop;

        public abstract boolean accept(E e);

    }

    // 内部使用的Node类
    protected class Node {

        E ele;

        Node left;

        Node right;

        Node parent;

        public Node(E ele, Node parent) {
            this.ele = ele;
            this.parent = parent;
        }

        public boolean isLeftNode() {
            return this.parent != null && (this.parent.left == this);
        }

        public boolean isRightNode() {
            return this.parent != null && (this.parent.right == this);
        }

        public Node sibling() {
            if (this != null) {
                if (isLeftNode()) {
                    return parent.right;
                }
                if (isRightNode()) {
                    return parent.left;
                }
            }
            return null;
        }

        public void rotateLeft() {
            Node next =  this.right;
            this.right = next.left;
            next.left = this;

            rotateAfter(this, next, this.right);
        }

        public void rotateRight() {
            Node next = this.left;
            this.left = next.right;
            next.right = this;

            rotateAfter(this, next, this.left);
        }

        public void rotate(Node b, Node c, Node d, Node e, Node f) {
            // 先处理，后面引用已经改变
            d.parent = parent;
            if (isLeftNode()) {
                parent.left = d;
            } else if (isRightNode()) {
                parent.right = d;
            } else {
                root = d;
            }

            b.right = c;
            if (c != null) {
                c.parent = b;
            }

            f.left = e;
            if (e != null) {
                e.parent = f;
            }

            d.left = b;
            if (b != null) {
                b.parent = d;
            }

            d.right = f;
            if (f != null) {
                f.parent = d;
            }

            d.left = b;
            if (b != null) {
                b.parent = d;
            }
        }

        public void rotateAfter(Node cur, Node next, Node node) {
            Node parent = cur.parent;
            next.parent = parent;
            if (parent == null) {
                root = next;
            } else if (cur.isLeftNode()) {
                cur.parent.left = next;
            } else if (cur.isRightNode()) {
                cur.parent.right = next;
            }
            cur.parent = next;
            if (node != null) {
                node.parent = cur;
            }
        }
    }

}
